package lanqiaobeiGuosai.bfs;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class 水壶问题 {
    public static void main(String[] args) {
        canMeasureWater(3,5,4);
    }
    public static boolean canMeasureWater(int x, int y, int target) {
        //这种情况一定不会满足
        if (x + y < target) return false;
        //全部加满 直接满足
        if (x + y == target) return true;

        //使用栈 模仿BFS的方式解决
        Deque<int[]> stack = new ArrayDeque();
        //初始化 默认里面的所有元素都是空的
        stack.push(new int[]{0, 0});
        //使用集合记录
        List<Long> list = new ArrayList();
        while (!stack.isEmpty()) {
            //看看当前的集合当中是否有对应的数据
            if (list.contains(hash(stack.peek()))) {
                stack.pop();
                //直接跳过
                continue;
            }
            int[] pop = stack.pop();
            int remind_x = pop[0];
            int remind_y = pop[1];
            //存储 使用hash值 从而保证一致性
            list.add(hash(pop));

            //满足一个即可 即使说和是大于的 那么一定是有一种情况是满足的
            if (remind_x == target || remind_y == target || remind_y + remind_x == target) {
                return true;
            }

            //六种情况找寻
            //1 添加X
            stack.push(new int[]{x, remind_y});
            //2 添加Y
            stack.push(new int[]{remind_x, y});
            //3.去除X 不动Y
            stack.push(new int[]{0,remind_y});
            stack.push(new int[]{remind_x,0});
            //X - > Y
            stack.push(new int[]{remind_x - Math.min(remind_x,y - remind_y),remind_y + Math.min(remind_x,y - remind_y)});
            // Y - > X
            stack.push(new int[]{remind_x + Math.min(x - remind_x,remind_y),remind_y - Math.min(x - remind_x,remind_y)});
        }
        return false;
    }

    /**
     * 哈希 确保对应的值不会出现重复
     * @param state
     * @return
     */
    public static long hash(int[] state) {
        return (long) state[0] * 1000001 + state[1];
    }
}
